Goldstein-price function
Contributed by: Benoît Legat
In this example, we consider the minimization of the Goldstein-price function.
using SumOfSquares
using DynamicPolynomialsCreate symbolic variables (not JuMP decision variables)
@polyvar x[1:2](DynamicPolynomials.Variable{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[x₁, x₂],)To use Sum-of-Squares Programming, we first need to pick an SDP solver, see here for a list of the available choices.
import Clarabel
using Dualization
model = SOSModel(dual_optimizer(Clarabel.Optimizer))A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: Dual model with Clarabel attachedCreate a JuMP decision variable for the lower bound
@variable(model, γ)$ γ $
f(x) is the Goldstein-Price function
f1 = x[1] + x[2] + 1
f2 = 19 - 14*x[1] + 3*x[1]^2 - 14*x[2] + 6*x[1]*x[2] + 3*x[2]^2
f3 = 2*x[1] - 3*x[2]
f4 = 18 - 32*x[1] + 12*x[1]^2 + 48*x[2] - 36*x[1]*x[2] + 27*x[2]^2
f = (1 + f1^2*f2) * (30 + f3^2*f4)\[ 600 + 720x_{2} + 720x_{1} + 3060x_{2}^{2} - 4680x_{1}x_{2} + 1260x_{1}^{2} + 12288x_{2}^{3} - 19296x_{1}x_{2}^{2} + 7344x_{1}^{2}x_{2} - 1072x_{1}^{3} + 14346x_{2}^{4} - 23616x_{1}x_{2}^{3} + 7776x_{1}^{2}x_{2}^{2} + 5784x_{1}^{3}x_{2} - 2454x_{1}^{4} + 1944x_{2}^{5} - 11880x_{1}x_{2}^{4} + 5040x_{1}^{2}x_{2}^{3} + 9840x_{1}^{3}x_{2}^{2} - 7680x_{1}^{4}x_{2} + 1344x_{1}^{5} - 4428x_{2}^{6} - 1188x_{1}x_{2}^{5} + 8730x_{1}^{2}x_{2}^{4} + 1240x_{1}^{3}x_{2}^{3} - 5370x_{1}^{4}x_{2}^{2} - 168x_{1}^{5}x_{2} + 952x_{1}^{6} - 648x_{2}^{7} + 1944x_{1}x_{2}^{6} + 3672x_{1}^{2}x_{2}^{5} - 3480x_{1}^{3}x_{2}^{4} - 4080x_{1}^{4}x_{2}^{3} + 2592x_{1}^{5}x_{2}^{2} + 1344x_{1}^{6}x_{2} - 768x_{1}^{7} + 729x_{2}^{8} + 972x_{1}x_{2}^{7} - 1458x_{1}^{2}x_{2}^{6} - 1836x_{1}^{3}x_{2}^{5} + 1305x_{1}^{4}x_{2}^{4} + 1224x_{1}^{5}x_{2}^{3} - 648x_{1}^{6}x_{2}^{2} - 288x_{1}^{7}x_{2} + 144x_{1}^{8} \]
Constraints f(x) - γ to be a sum of squares
con_ref = @constraint(model, f >= γ)
@objective(model, Max, γ)
optimize!(model)-------------------------------------------------------------
Clarabel.jl v0.6.0 - Clever Acronym
(c) Paul Goulart
University of Oxford, 2022
-------------------------------------------------------------
problem:
variables = 45
constraints = 121
nnz(P) = 0
nnz(A) = 121
cones (total) = 2
: Zero = 1, numel = 1
: PSDTriangle = 1, numel = 120
settings:
linear algebra: direct / qdldl, precision: Float64
max iter = 200, time limit = Inf, max step = 0.990
tol_feas = 1.0e-08, tol_gap_abs = 1.0e-08, tol_gap_rel = 1.0e-08,
static reg : on, ϵ1 = 1.0e-08, ϵ2 = 4.9e-32
dynamic reg: on, ϵ = 1.0e-13, δ = 2.0e-07
iter refine: on, reltol = 1.0e-13, abstol = 1.0e-12,
max iter = 10, stop ratio = 5.0
equilibrate: on, min_scale = 1.0e-04, max_scale = 1.0e+04
max iter = 10
iter pcost dcost gap pres dres k/t μ step
---------------------------------------------------------------------------------------------
0 6.0000e+02 6.0000e+02 0.00e+00 6.51e-01 4.57e-01 1.00e+00 1.02e+04 ------
1 -3.0355e+03 -2.4055e+03 2.62e-01 1.69e-01 1.33e-01 6.30e+02 2.58e+03 8.06e-01
2 -4.5486e+02 -2.1780e+02 1.09e+00 2.38e-02 2.39e-02 2.37e+02 5.36e+02 8.67e-01
3 3.2891e+01 7.6205e+01 1.32e+00 3.59e-03 3.47e-03 4.33e+01 9.46e+01 8.76e-01
4 2.7894e+01 3.5220e+01 2.63e-01 6.65e-04 6.22e-04 7.33e+00 1.84e+01 8.59e-01
5 1.2781e+01 1.9102e+01 4.95e-01 3.55e-04 4.58e-04 6.32e+00 1.16e+01 5.36e-01
6 5.6656e+00 6.5505e+00 1.56e-01 5.37e-05 7.07e-05 8.85e-01 1.88e+00 8.72e-01
7 4.1810e+00 4.5446e+00 8.70e-02 1.90e-05 2.68e-05 3.64e-01 6.80e-01 8.09e-01
8 3.4403e+00 3.5518e+00 3.24e-02 6.41e-06 8.82e-06 1.12e-01 2.39e-01 7.54e-01
9 3.0921e+00 3.1107e+00 6.02e-03 1.22e-06 1.64e-06 1.86e-02 4.73e-02 9.05e-01
10 3.0507e+00 3.0623e+00 3.79e-03 9.90e-07 9.38e-07 1.16e-02 2.75e-02 5.97e-01
11 3.0083e+00 3.0101e+00 5.87e-04 2.86e-07 1.50e-07 1.77e-03 4.46e-03 8.80e-01
12 3.0049e+00 3.0059e+00 3.41e-04 5.46e-07 8.70e-08 1.02e-03 2.58e-03 5.38e-01
13 3.0009e+00 3.0011e+00 7.63e-05 4.75e-07 1.68e-08 2.29e-04 7.26e-04 9.20e-01
14 3.0008e+00 3.0011e+00 7.36e-05 3.34e-06 1.61e-08 2.21e-04 6.34e-04 5.82e-02
15 3.0005e+00 3.0007e+00 5.06e-05 2.22e-06 1.06e-08 1.52e-04 4.21e-04 4.65e-01
16 3.0005e+00 3.0006e+00 4.41e-05 1.87e-06 9.11e-09 1.32e-04 3.66e-04 2.14e-01
17 3.0003e+00 3.0004e+00 3.21e-05 1.34e-06 6.44e-09 9.65e-05 2.69e-04 4.25e-01
18 3.0003e+00 3.0004e+00 2.75e-05 1.68e-06 5.50e-09 8.25e-05 2.03e-04 1.54e-01
19 3.0002e+00 3.0003e+00 2.17e-05 1.46e-06 4.32e-09 6.51e-05 1.60e-04 2.99e-01
20 3.0002e+00 3.0002e+00 1.90e-05 1.24e-06 3.79e-09 5.71e-05 1.36e-04 1.28e-01
21 3.0002e+00 3.0002e+00 1.87e-05 1.17e-06 3.71e-09 5.60e-05 1.34e-04 5.42e-02
22 3.0000e+00 3.0000e+00 1.86e-06 1.17e-07 3.70e-10 5.58e-06 1.39e-05 9.07e-01
23 3.0000e+00 3.0000e+00 4.70e-07 3.92e-07 9.18e-11 1.41e-06 3.68e-06 8.25e-01
24 3.0000e+00 3.0000e+00 2.04e-07 1.54e-07 3.86e-11 6.11e-07 1.52e-06 7.04e-01
25 3.0000e+00 3.0000e+00 2.04e-07 1.54e-07 3.86e-11 6.11e-07 1.52e-06 0.00e+00
---------------------------------------------------------------------------------------------
Terminated with status = solved (reduced accuracy)
solve time = 217msThe lower bound found is 3
solution_summary(model)* Solver : Dual model with Clarabel attached
* Status
Result count : 1
Termination status : ALMOST_OPTIMAL
Message from the solver:
"ALMOST_SOLVED"
* Candidate solution (result #1)
Primal status : NEARLY_FEASIBLE_POINT
Dual status : NEARLY_FEASIBLE_POINT
Objective value : 3.00000e+00
Dual objective value : 3.00000e+00
* Work counters
Solve time (sec) : 2.17321e-01
Barrier iterations : 25
The moment matrix is as follows, we can already see the global minimizer [0, -1] from the entries (2, 1) and (3, 1). This heuristic way to obtain solutions to the polynomial optimization problem is suggested in [L09, (6.15)].
[L09] Laurent, Monique. Sums of squares, moment matrices and optimization over polynomials. Emerging applications of algebraic geometry (2009): 157-270.
ν = moment_matrix(con_ref)MomentMatrix with row/column basis:
MonomialBasis([1, x[2], x[1], x[2]^2, x[1]*x[2], x[1]^2, x[2]^3, x[1]*x[2]^2, x[1]^2*x[2], x[1]^3, x[2]^4, x[1]*x[2]^3, x[1]^2*x[2]^2, x[1]^3*x[2], x[1]^4])
And entries in a 15×15 SymMatrix{Float64}:
1.0000000017942992 -0.999989143710501 … 1.7053053568112501e-7
-0.999989143710501 0.9999783243534897 6.797989423469114e-8
1.580102593106209e-5 -1.5771972745812904e-5 2.79696701840826e-7
0.9999783072999893 -0.9999674674920328 4.647622407969194e-5
-1.5786666526493362e-5 1.5803029613779264e-5 4.876404311575872e-5
1.1323687290922323e-7 -3.750689669898932e-8 … 9.450720417176097e-5
-0.9999674117632373 0.9999566722211841 -0.0006788961387083221
1.5800448377331057e-5 -1.579995109911538e-5 -0.0010861136843415642
7.342911073028707e-9 1.4323043649043317e-7 -0.001443038296573526
8.20862258382363e-8 6.51535261135398e-8 -0.0021945096989402974
0.9999566700632712 -0.9999458226585068 … 0.715987679666811
-1.578574352355621e-5 1.5761546673647885e-5 -0.0410781652118392
7.323462890186348e-8 -6.420239773375324e-8 1.0505421700738642
6.801985355837143e-8 -5.194381992715694e-9 0.46168908097995054
1.7053053568112501e-7 6.797989423469114e-8 1.8018743040423588Many entries of the matrix actually have the same moment. We can obtain the following list of these moments without duplicates (ignoring when difference of entries representing the same moments is below 1e-5)
μ = measure(ν, atol = 1e-5)Measure{Float64, DynamicPolynomials.Monomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}, DynamicPolynomials.MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}}([1.0000000017942992, -0.999989143710501, 1.580102593106209e-5, 0.9999783072999893, -1.5786666526493362e-5, 1.1323687290922323e-7, -0.9999674117632373, 1.5800448377331057e-5, 7.342911073028707e-9, 8.20862258382363e-8 … -0.0021945096989402974, 1.5012396326670379, -0.3664568576392168, 0.5672190390117505, -0.26573151069000334, 0.715987679666811, -0.0410781652118392, 1.0505421700738642, 0.46168908097995054, 1.8018743040423588], DynamicPolynomials.Monomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[1, x₂, x₁, x₂², x₁x₂, x₁², x₂³, x₁x₂², x₁²x₂, x₁³ … x₁⁷, x₂⁸, x₁x₂⁷, x₁²x₂⁶, x₁³x₂⁵, x₁⁴x₂⁴, x₁⁵x₂³, x₁⁶x₂², x₁⁷x₂, x₁⁸])The truncated moment matrix can then be obtained as follows
ν_truncated = moment_matrix(μ, monomials(x, 0:3))MomentMatrix with row/column basis:
MonomialBasis([1, x[2], x[1], x[2]^2, x[1]*x[2], x[1]^2, x[2]^3, x[1]*x[2]^2, x[1]^2*x[2], x[1]^3])
And entries in a 10×10 SymMatrix{Float64}:
1.0000000017942992 -0.999989143710501 … 8.20862258382363e-8
-0.999989143710501 0.9999783072999893 6.801985355837143e-8
1.580102593106209e-5 -1.5786666526493362e-5 1.7053053568112501e-7
0.9999783072999893 -0.9999674117632373 -5.194381992715694e-9
-1.5786666526493362e-5 1.5800448377331057e-5 6.797989423469114e-8
1.1323687290922323e-7 7.342911073028707e-9 … 2.79696701840826e-7
-0.9999674117632373 0.9999566700632712 1.7057184431936546e-5
1.5800448377331057e-5 -1.578574352355621e-5 4.647622407969194e-5
7.342911073028707e-9 7.323462890186348e-8 4.876404311575872e-5
8.20862258382363e-8 6.801985355837143e-8 9.450720417176097e-5Let's check if the flatness property is satisfied. The rank of ν_truncated seems to be 1:
using LinearAlgebra
LinearAlgebra.svdvals(Matrix(ν_truncated.Q))
LinearAlgebra.rank(Matrix(ν_truncated.Q), rtol = 1e-3)
svdvals(Matrix(ν_truncated.Q))10-element Vector{Float64}:
3.9998738488272467
0.00014858202106434175
2.9538170321778437e-5
3.9445311450139666e-7
1.298822750570064e-7
7.383992070844883e-8
7.137853776215193e-8
5.6548076457455015e-8
2.2012043333595885e-8
3.365360038791725e-9The rank of ν is clearly higher than 1, closer to 3:
svdvals(Matrix(ν.Q))15-element Vector{Float64}:
5.196427254487122
2.7012010863685187
1.738742316554198
0.00038475922885237426
0.00010800491691338999
2.7579831986545214e-5
2.3799442037633358e-5
4.5451574756198407e-7
1.4168137174886528e-7
2.9359880377630318e-8
1.0751169947369091e-8
1.4669490520969313e-9
5.433360224336174e-10
2.399183381207747e-11
1.8344496494568505e-11Even if the flatness property is not satisfied, we can still try extracting the minimizer with a low rank decomposition of rank 3. We find the optimal solution again doing so:
atomic_measure(ν, FixedRank(3))Atomic measure on the variables x[1], x[2] with 1 atoms:
at [1.581694412093348e-5, -0.9999891631593412] with weight 1.033433351536792This page was generated using Literate.jl.